package com.dljd.javase.t6;

import java.util.Arrays;

/*
数组排序知识演示案例代码
 */
public class SortDemo {

    /**
     * 冒泡排序（升序）
     * @param arr
     */
    public static void sort(int[] arr) {
        // 外侧循环：用于控制比较趟数。
        for(int i = 0; i < arr.length - 1; i++) {
            // 内侧循环：用于每趟循环相邻两个元素比较的次数
            for(int j = 0; j < arr.length - i - 1; j++) {
                // b)如果前一个元素大于后一个元素，则交换位置
                if(arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 二分法查找
     * @param arr 需要查找的数组
     * @param value 需要查找的元素值
     * @return 如果返回值为正数，则证明找到；如果返回-1，则证明没找到。
     */
    public static int binarySearch(int[] arr, int value) {
        // 最小索引
        int min = 0;
        // 最大索引
        int max = arr.length - 1;
        // 开始循环查找
        while(true) {
            // 获取中间索引
            int mid = (min + max)/2;
            // 如果arr[mid]>value,则证明在上半区
            if(arr[mid] > value) {
                // 更新max的值
                max = mid - 1;
            }
            // 如果arr[mid]<value,则证明在下半区
            else if(arr[mid] < value) {
                // 更新min的值
                min = mid + 1;
            }
            // 如果arr[mid]==value,则证明找到
            else {
                return mid;
            }
            // 如果min>max,则证明没找到该值
            if(min > max) {
                return -1;
            }
        }
    }

    public static void main(String[] args) {
//        int[] arr = {3, 5, 1, 2, 4};
//        System.out.println(Arrays.toString(arr));
//        sort(arr);
//        System.out.println(Arrays.toString(arr));

        int[] nums={2,5,23,38,40,55,13,18,32,34};
        int value=18;
        int weizhi=binarySearch(nums,value);
        System.out.println("位置是"+weizhi);
    }
}
